import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-15
 * Time: 23:28
 */
class Solution {
//     回溯 + 交换
//     (因为基于交换, 所以可以到最后再往 list 里面一下添加所有元素)
//     交换是 与 该元素后面的所有元素 都交换一遍
//     所以要用循环
//     注意: 交换时不要出现死循环(可能出现 两个位置一直来回交换 的情况)
//     即 交换过之后 下一个递归的位置是 index+1
    public int[] arr;
    public int length;
    public List<List<Integer>> lists=new ArrayList<>();
    public List<Integer> list =new ArrayList<>();
    public void dfs(int index){
        if(index==this.length){
            lists.add(new ArrayList<>(list));
            return;
        }
        for(int i=index;i<this.length;i++){
            swap(index, i);
            list.add(this.arr[index]);
            // 这里　是 index+1
            dfs(index+1);
            list.remove(list.size()-1);
            swap(index, i);
        }
    }
    public void swap(int index1, int index2){
        int temp=this.arr[index1];
        this.arr[index1]=this.arr[index2];
        this.arr[index2]=temp;
    }
    public List<List<Integer>> permute(int[] nums) {
        this.arr=nums;
        this.length=nums.length;
        dfs(0);
        return lists;
    }
}
